What are some examples of bad Big-Oh style?

	O(2N)
	O(N + 2)
	O(N^2 + N)



Classwork
You may work together with a partner.
Give a Big-Oh analysis of the running time for each program
fragment. (problem 5.15a)

	for ( int i = 0; i < n; i++ )
	    sum++;

	for ( int i = 0; i < n; i += 2 )
	    sum++;

	for ( int i = 0; i < n; i++ )
	    for ( int j = 0; j < n; j++ )
	    	sum++;

	for ( int i = 0; i < n; i++ )
	    sum++;
	for ( int j = 0; j < n; j++ )
	    sum++;

	for ( int i = 0; i < n; i++ )
	    for ( int j = 0; j < n*n; j++ )
	    	sum++;

	for ( int i = 0; i < n; i++ )
	    for ( int j = 0; j < i; j++ )
	    	sum++;

	for ( int i = 0; i < n; i++ )
	    for ( int j = 0; j < n*n; j++ )
                for ( int k = 0; k < j; k++ )
		    sum++;


The inside loop in the following code fragment does not always repeat n times.
Does this mean the code has a Big-Oh bound that is smaller than O(n^2)?

	for ( int i = 0; i < n; i++ )
	    for ( int j = 0; j < i; j++ )
	    	sum++;




Worst-Case vs Average-Case


Is it possible for an algorithm to run faster for some inputs than for others?


Suppose you sort lists A and B using the same sorting algorithm.
Could the algorithm be faster for one of the lists?

	A = 0 1 2 3 4 9 5 6 7 8
	B = 5 9 1 8 0 2 6 4 7 3


What's a Worst-case bound?

	longest time over all inputs of size N


What's an Average-case bound?

	average time over all inputs of size N




Comparison of Growth Rates


How do linear, quadratic, and cubic growth rates compare when given
inputs of increasing size?


If an algorithm takes time 1 second to solve a problem of size 10,
how long does it take to solve a problem of size 1000?

	Linear (T(N) = c*N)

		T(1000)/1000 = T(10)/10
		T(1000)/1000 = 1/10
		T(1000) = 1000/10
		T(1000) = 100

	Quadratic (T(N) = c*N^2)

		T(1000)/(1000^2) = T(10)/(10^2)
		T(1000)/(1000*1000) = 1/(10*10)
		T(1000) = (1000*1000)/(10*10)
		T(1000) = 100*100 = 10000

	Cubic (T(N) = c*N^3)

		T(1000)/(1000^3) = T(10)/(10^3)
		T(1000)/(1000*1000*1000) = 1/(10*10*10)
		T(1000) = (1000*1000*1000)/(10*10*10)
		T(1000) = 100*100*100 = 1000000


Classwork
You may work together with a partner.
An algorithm takes 0.5 ms for input size 100. (problem 5.11acd)
How long will it take for input size 500 if the running time is:

	a. linear

		T(500)/500 = T(100)/100
		T(500)/500 = 0.5ms/100
		T(500) = 500*0.5ms/100
		T(500) = 5*0.5ms
		T(500) = 2.5ms

	c. quadratic

		T(500)/(500^2) = T(100)/(100^2)
		T(500)/(500*500) = 0.5ms/(100*100)
		T(500) = (500*500)*0.5ms/(100*100)
		T(500) = 5*5*0.5ms
		T(500) = 12.5ms

	d. cubic

		T(500)/(500^3) = T(100)/(100^3)
		T(500)/(500*500*500) = 0.5ms/(100*100*100)
		T(500) = (500*500*500)*0.5ms/(100*100*100)
		T(500) = 5*5*5*0.5ms
		T(500) = 62.5ms


If an algorithm takes 10 seconds to solve a problem of size 100,
how large a problem can you solve in 1000 seconds?

	Linear (T(N) = c*N)

		N/T(N) = 100/T(10)
		N/1000 = 100/10
		N = 1000*100/10
		N = 10000

	Quadratic (T(N) = c*N^2)

		(N^2)/T(N) = (100^2)/T(10)
		(N^2)/1000 = (100*100)/10
		(N^2) = 1000*(100*100)/10
		(N^2) = 1000000
		N = 1000

	Cubic (T(N) = c*N^3)

		(N^3)/T(N) = (100^3)/T(10)
		(N^3)/1000 = (100*100*100)/10
		(N^3) = 1000*(100*100*100)/10
		(N^3) = 100000000
		N = 100 * cube-root(100) (4.65)


Suppose you have 1000 seconds and the coefficient 
of the dominant term in T(N) is 10^-9 seconds.
(A CPU this fast may exist in the next 5-10 years.)
How large a problem can you solve?

	Linear (T(N) = c*N)

		1000 = 10^-9 * N
		N = 1000 / 10^-9
		N = 10^12
		could work up to about a trillion

	Quadratic (T(N) = c*N^2)

		1000 = 10^-9 * N^2
		N^2 = 1000 / 10^-9
		N^2 = 10^12
		N = 10^6
		could work up to about a million

	Cubic (T(N) = c*N^3)

		1000 = 10^-9 * N^3
		N^3 = 1000 / 10^-9
		N^3 = 10^12
		N = 10^4
		could work up to about 10 thousand